#include "heap.h"

void HPInit(Heap* shp)
{
	assert(shp);
	shp->a = NULL;
	shp->size = shp->capacity = 0;
}

void HPDestrory(Heap* shp)
{
	assert(shp);
	assert(!HPEmpty(shp));
	free(shp->a);
	shp->a = NULL;
	shp->size = shp->capacity = 0;
}

void Swap(HPDataType* tmp1, HPDataType* tmp2)
{
	HPDataType tmp = *tmp1;
	*tmp1 = *tmp2;
	*tmp2 = tmp;
}

void AdjustUp(Heap* shp, HPDataType child)
{
	HPDataType parent = (child - 1) / 2;
	while (child > 0)
	{
		if (shp->a[parent] > shp->a[child])
		{
			Swap(&shp->a[parent], &shp->a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else break;
	}
}

void HPPush(Heap* shp, HPDataType x)
{
	assert(shp);
	if (shp->size == shp->capacity)
	{
		int newCapacity = shp->capacity == 0 ? 4 : 2 * shp->capacity;
		shp->a = (HPDataType*)realloc(shp->a, sizeof(HPDataType) * newCapacity);
		if (shp->a == NULL)	perror("realloc fail:");
		else shp->capacity = newCapacity;
	}
	shp->a[shp->size] = x;
	AdjustUp(shp, shp->size);
	shp->size++;
}

void AdjustDown(Heap* shp, HPDataType parent)
{
	HPDataType leftChild = 2 * parent + 1;
	HPDataType rightChild = 2 * parent + 2;
	while (leftChild < shp->size-1)
	{
		HPDataType smallChild;
		if (rightChild == shp->size - 1)
			smallChild = leftChild;
		else smallChild = shp->a[leftChild] < shp->a[rightChild] ? leftChild : rightChild;
		if (shp->a[smallChild] < shp->a[parent])
		{
			Swap(&shp->a[smallChild], &shp->a[parent]);
			parent = smallChild;
			leftChild = 2 * parent + 1;
			rightChild = 2 * parent + 2;
		}
		else break;
	}
}

void HPPop(Heap* shp)
{
	assert(shp);
	assert(shp->size >= 1);
	Swap(&shp->a[0], &shp->a[shp->size - 1]);
	shp->size--;
	AdjustDown(shp, 0);
}

void HPPrint(Heap* shp)
{
	assert(shp);
	assert(!HPEmpty(shp));
	for (int i = 0; i < shp->size; i++)
	{
		printf("%d ", shp->a[i]);
	}
	printf("\n");
}

bool HPEmpty(Heap* shp)
{
	return shp->size == 0;
}
